package depta.treematching;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;

import org.htmlparser.Node;
import org.htmlparser.nodes.TagNode;
import org.htmlparser.util.NodeList;
import org.lobobrowser.html.UserAgentContext;
import org.lobobrowser.html.parser.DocumentBuilderImpl;
import org.lobobrowser.html.test.SimpleUserAgentContext;
import org.xml.sax.InputSource;

import util.nodecloner.ChildFinder;
import util.nodecloner.NodeCloner;

import com.google.gdata.util.common.base.Pair;

import depta.DOMTree.TreeBuilder;

public class EnhancedSimpleTreeMatching {

	private Map<Node, Map<Node, double[][]>> map;

	public EnhancedSimpleTreeMatching(){
		map = new HashMap<Node, Map<Node,double[][]>>();
	}
	
	public double ESTM(Node node1, Node node2){
		
		if (match(node1,node2)){
			
			double[][] M = generateMMatrix(node1,node2);
			
			for (int i = 1; i < M.length; i++) {
				for (int j = 1; j < M[i].length; j++) {
					M[i][j] = Math.max(M[i][j-1], Math.max(M[i-1][j], M[i-1][j-1] + ESTM(ChildFinder.getChildren(node1).elementAt(i-1), ChildFinder.getChildren(node2).elementAt(j-1))));
				}
			}
			
			getMap(node1).put(node2,M);
			
			return M[M.length-1][M[0].length-1] + 1 + getContentSimilarity(node1,node2); 
			
		}else{
			return 0;
		}
		
	}

	private boolean match(Node t1, Node t2) {
		
		if (t1 instanceof TagNode){
			
			if (t2 instanceof TagNode){
				
				TagNode tt1 = (TagNode)t1;
				
				TagNode tt2 = (TagNode)t2;
				
				boolean sameTag = tt1.getTagName().equals(tt2.getTagName());
				
				if (!sameTag)
					return false;
				
				if (!tt1.getTagName().equals("")){
					return true;
				}else{
					System.out.println("EMPTY!!!!");
				}
				
				return childMatch(ChildFinder.getChildren(tt1),ChildFinder.getChildren(tt2)) && !visualConflict(t1,t2);

			}
		}
		
		return false;
		
	}

	private boolean childMatch(NodeList child1, NodeList child2) {
		
		if (Math.abs(child1.size()-child2.size())>1){
			return false;
		}
		
		List<String> children1 = getStringChild(child1);
		
		List<String> children2 = getStringChild(child2);
		
		for (String tag : children2) {
			children1.remove(tag);
		}
		
		return children1.size()<=1;
		
	}

	private List<String> getStringChild(NodeList child1) {
		
		List<String> ret = new ArrayList<String>();
		
		for (int i = 0; i < child1.size(); i++) {
			Node n1 = child1.elementAt(i);
			if (n1 instanceof TagNode){
				ret.add(((TagNode)n1).getTagName());
			}else{
				ret.add(n1.getClass().toString());
			}
		}
		
		return ret;
	}

	private Map<Node, double[][]> getMap(Node t1) {
		
		Map<Node,double[][]> ret = map.get(t1);
		
		if (ret == null){
			ret = new HashMap<Node, double[][]>();
			map.put(t1,ret);
		}
		return ret;
	}

	private double getContentSimilarity(Node t1, Node t2) {
		
		if (!ChildFinder.hasChildren(t1) && !ChildFinder.hasChildren(t2)){
			
			String text1 = t1.getText();
			String text2 = t2.getText();
			
			String[] spl1 = text1.split(" ");
			String[] spl2 = text2.split(" ");

			List<String> lcs = LCS.LongestCommonSubsequence(spl1, spl2);
					
			double factor = (double)Math.max(spl1.length, spl2.length);
			
			if (factor==0)
				factor=1;
			
			return ((double)lcs.size()/factor);
			
		}
		
		return 0.0; 

	}

	private double[][] generateMMatrix(Node t1, Node t2) {
		
		int m = ChildFinder.getChildren(t1).size()+1;
		int n = ChildFinder.getChildren(t2).size()+1;
		
		double[][] M = new double[m][n];
		
		for (int i = 0; i < m; i++) {
			M[i][0] = 0;
		}
		for (int i = 0; i < n; i++) {
			M[0][i] = 0;
		}

		return M;
		
	}

	private boolean visualConflict(Node t1, Node t2) {
		// TODO Auto-generated method stub
		return false;
	}

	public Pair<Node,Node> getCalculatedMatch(Node t1, Node t2) {
		
		if (!match(t1,t2)){ //only for the first case.
			return null;
		}
		
		return getMatch(t1,t2);

	}

	private Pair<Node,Node> getMatch(Node t1, Node t2) {
		
		//They are here because they match.
		
		double[][] M = map.get(t1).get(t2);
		
        int s1position = ChildFinder.getChildren(t1).size(), s2position = ChildFinder.getChildren(t2).size();
        
        Node ct1 = NodeCloner.clone(t1, false, false);
        
        Node ct2 = NodeCloner.clone(t1, false, false);
 
        List<Pair<Node,Node>> children = new ArrayList<Pair<Node,Node>>();
        
        while (s1position != 0 && s2position != 0)
        {
        	
        		Node c1 = ChildFinder.getChildren(t1).elementAt(s1position - 1);
        		
        		Node c2 = ChildFinder.getChildren(t2).elementAt(s2position - 1);
        	
        		if (isAMatch(c1,c2,M[s1position-1][s2position - 1],M[s1position][s2position - 1],M[s1position-1][s2position]))
                {
                	    
        			children.add(0,getMatch(c1, c2));
                	                          	
                    s1position--;
                    s2position--;
                }
                else if (M[s1position][s2position - 1] >= M[s1position - 1][s2position])
                {
                        s2position--;
                }
                else
                {
                        s1position--;
                }

        }
		
        for (Pair<Node, Node> pair : children) {
			ChildFinder.getChildren(ct1).add(pair.first);
			ChildFinder.getChildren(ct2).add(pair.second);
		}
        
        return new Pair<Node,Node>(ct1,ct2);

		
	}

	private boolean isAMatch(Node node1, Node node2, double diag, double up, double left) {
		
		if (match(node1, node2)){
					
			double[][] M = map.get(node1).get(node2);
			
			double estmValue = M[ChildFinder.getChildren(node1).size()][ChildFinder.getChildren(node2).size()];
			
			if (diag + estmValue > up && diag + estmValue > left)
				return true;
			
			return false;
			
		}
		
		return false;
		
	}

	
	
}
